package com.agile.leetcode.middle.minAddToMakeValid;


import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 使括号有效的最少添加
 * 给定一个由 '(' 和 ')' 括号组成的字符串 S，我们需要添加最少的括号（ '(' 或是 ')'，可以在任何位置），以使得到的括号字符串有效。
 * <p>
 * 从形式上讲，只有满足下面几点之一，括号字符串才是有效的：
 * <p>
 * 它是一个空字符串，或者
 * 它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
 * 它可以被写作 (A)，其中 A 是有效字符串。
 * 给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入："())"
 * 输出：1
 * 示例 2：
 * <p>
 * 输入："((("
 * 输出：3
 * 示例 3：
 * <p>
 * 输入："()"
 * 输出：0
 * 示例 4：
 * <p>
 * 输入："()))(("
 * 输出：4
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/minimum-add-to-make-parentheses-valid
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author:ChenZhangKun
 * @Date: 2021/4/7 22:38
 */
public class MinAddToMakeValid {
    public static void main(String[] args) {
        MinAddToMakeValid minAddToMakeValid = new MinAddToMakeValid();
        String s = "()))((";
        System.out.println(minAddToMakeValid.minAddToMakeValid(s));
    }

    public int minAddToMakeValid(String s) {
        // 创建map
        Map<Character, Character> map = new HashMap<>();
        // 创建括号
        map.put(')', '(');
        // 创建栈
        Stack<Character> stack = new Stack<>();
        // 定义总数
        int result = 0;
        // 遍历
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 是否是闭括号
            if (map.containsKey(c)) {
                // 拿到栈顶
                char top = stack.isEmpty() ? '#' : stack.pop();
                // 栈顶是否是对应的元素
                if (top == map.get(c)) {
                    continue;
                } else {
                    result++;
                }
            } else {
                stack.push(c);
            }
        }
        // 加上栈中剩余的数
        return result + stack.size();
    }
}
